package com.yahoo.labs.snow.solver;

import it.unimi.dsi.fastutil.ints.IntOpenHashSet;

import com.yahoo.labs.snow.ProblemInstance;

/**
 * Iteratively picks all elements as pivots, starting from the lowest-numbered one.
 * Uses a greedy pickFlake() to find the best one.
 * 
 * @author chato
 *
 */
public class ExhaustiveSOBOSolver extends SnowflakesOneByOneSolver {

	public ExhaustiveSOBOSolver(ProblemInstance problem) {
		super(problem);
		SNOWFLAKE_MEMBERS_CAN_BE_PIVOTS = true;
	}

	@Override
	int getPivot(IntOpenHashSet pivotsUsed, IntOpenHashSet possiblePivots) {
		int minPivot = Integer.MAX_VALUE;
		
		for( int possiblePivot: possiblePivots ) {
			if( ! pivotsUsed.contains(possiblePivot) ) {
				if( possiblePivot < minPivot ) {
					minPivot = possiblePivot;
				}
			}
		}
				
		if( minPivot == Integer.MAX_VALUE ) {
			throw new IllegalStateException("Could not get a valid pivot" );
		}
		return minPivot;
	}

	@Override
	public int numToProduce(int requestedSnowflakes) {
		return problem.numNodes();
	}
}
